For a user to search for images, the images are generally stored in databases with corresponding text phrases such as titles, keywords or captions. The user's search is then based on an entered keyword, and the search returns images if the entered keyword matches one of the text phrases. However, with larger sets of image data, it becomes impractical to store all of the images with text indexes to correspond with each image. It is also highly burdensome for someone to manually attribute specific titles, keywords and captions to each one. Furthermore, text-based searches have their inherent drawbacks as well. To overcome the limitations of text searches, attempts have been made to utilize image-based searches.
Earth Mover's Distance (EMD) is a distance between two distributions, which reflects the minimal amount of work that must be performed to transform one distribution into the other by moving “distribution mass” around. There have been projects implementing EMD in a variety of applications including applications with image databases, specifically color and texture.
U.S. Pat. No. 6,710,822 to Walker, et al. discloses providing an image-voice processing apparatus for search based on the similarity of segments of various levels in various video data. Walker further discloses standards for measuring dissimilarity including using the EMD in the case of color short messages for still pictures in applications of the distance measuring method.
U.S. Pat. No. 6,760,724 to Chakrabarti, et al. discloses a method for querying electronic data. The query method comprises creating wavelet-coefficient synopses of the electronic data and then querying the synopses in the wavelet-coefficient domain to obtain a wavelet-coefficient query result. The wavelet-coefficient query result is then rendered to provide an approximate result. The EMD error metric was used for computing the dissimilarity between two distributions of points and applied to computing distances between images in a database. The idea was to formulate the distance between two (multi)sets as a bipartite network flow problem, where the objective function incorporates the distance in the values of matched elements and the flow captures the distribution of element counts.
However, the problem with EMD and other existing methodologies is that they do not always correspond to how humans perceive the distance between two distributions.